#include <bits/stdc++.h>
using namespace std;
//快速幂：快速求出a的b次方
int quickm(int a,int b){
  int ans=1;
  int rns=a;
  while(b){
    if(b&1){//b&1相当于判断它是奇数还是偶数，若为奇数则为1
      ans*=rns;
    }
    rns*=rns;
    //b>>=1;这两种写法都可以
    b/=2;
  }
  return ans;
}

//快速幂取模
//表示为a的b次方，再对c取模
int quickmm(int a,int b,int c){
  int ans=1;
  int rns=a;
  while(b){
    if(b&1){
      ans=(rns*ans)%c;
    }
    rns=(rns*rns)%c;
    //b>>=1;这两种写法都可以
    b/=2;
  }
  return ans;
}
int main() {
  cout<<quickm(2,3)<<endl;//8

  cout<<quickmm(2,3,7)<<endl;//1
  return 0;
}
